package 刷题.leedcode20;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

import static javax.swing.UIManager.put;

//有效的括号
//利用栈来解
//三个栈，分别储存三种左括号，然后遇到匹配的右括号一一取出
public class Solution {
    public boolean isValid(String s) {
        int n = s.length();
        if(n % 2 == 1){
            return false;
        }
        Map<Character,Character> pairs = new HashMap<Character,Character>(){{
            put(')','(');
            put(']','[');
            put('}','{');
        }};
        Deque<Character> stack = new LinkedList<Character>();
        for(int i = 0;i < n;i++){
            char ch = s.charAt(i);
            if(pairs.containsKey(ch)){//查看pairs中是否存在key
                if(stack.isEmpty() || stack.peek() != pairs.get(ch)){
                    return false;
                }
                stack.pop();//移除栈顶元素
            }else{
                stack.push(ch);//在栈顶新ta添加一个元素
            }
        }
        return stack.isEmpty();//true false
    }
}
